Pascal's Triangle



In [1]:

    
import sys; sys.path.append('../..')
from puzzles import leet_puzzle
leet_puzzle('pascals-triangle')









    




Source : https://leetcode.com/problems/pascals-triangle
Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]







Array





 (E) Pascal's Triangle II

Naive Solution

Given a piece of paper and 10 minutes this was the naive solution I could come up with, however it is horribly inefficient calculating all previous rows in order to get the current row. The time complexity is O((n² + n)/2) and space complexity is O(2n). However it does give the expected output.



In [8]:

    
def pascals_triangle(k):
    prev_row = None
    for r in xrange(k+1):
        row = [None] * r
        for c in xrange(r):
            if c == 0 or c == r-1:
                row[c] = 1
            else:
                row[c] = prev_row[c] + prev_row[c-1]
        prev_row = row
    return row


for k in xrange(1, 10):
    print pascals_triangle(k)









    



[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]



In [8]:

    
%%timeit
pascals_triangle(40)









    



1000 loops, best of 3: 224 µs per loop

Optimised Solution

However it is possible to do this in O(n) space and O(n/2) time complexity:



In [16]:

    
def pascals_triangle_2(k):
    
    k = k - 1
    
    row = [1]
    
    # only need to calculate half of the row, since the triangle is
    # symmetric
    for n in xrange(k / 2):
        row.append(row[n] * (k - n) / (n + 1))
        
    # middle element is repeated only for odd values of k
    r = list(reversed(row))
    r = r[1:] if k % 2 == 0 else r
    
    return row + r


for k in xrange(1, 10):
    print pascals_triangle_2(k)









    



[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]



In [19]:

    
%%timeit
pascals_triangle_2(40)









    



100000 loops, best of 3: 5.94 µs per loop

Corner Cases

There are a number of corner cases which should be considered, for example passing in a negative integer, or passing a string for example, but the typical corner case with pascals triangle is an integer overflow when dealing with large numbers. In python however integers have arbitrary size, and expand as required, for example:



In [25]:

    
pascals_triangle_2(50)









    Out[25]:





[1,
 49,
 1176,
 18424,
 211876,
 1906884,
 13983816,
 85900584,
 450978066L,
 2054455634L,
 8217822536L,
 29135916264L,
 92263734836L,
 262596783764L,
 675248872536L,
 1575580702584L,
 3348108992991L,
 6499270398159L,
 11554258485616L,
 18851684897584L,
 28277527346376L,
 39049918716424L,
 49699896548176L,
 58343356817424L,
 63205303218876L,
 63205303218876L,
 58343356817424L,
 49699896548176L,
 39049918716424L,
 28277527346376L,
 18851684897584L,
 11554258485616L,
 6499270398159L,
 3348108992991L,
 1575580702584L,
 675248872536L,
 262596783764L,
 92263734836L,
 29135916264L,
 8217822536L,
 2054455634L,
 450978066L,
 85900584,
 13983816,
 1906884,
 211876,
 18424,
 1176,
 49,
 1]

With very large numbers in a python solution you will eventually run out of memory, for example:



In [18]:

    
import sys
result2 = pascals_triangle_2(sys.maxint - 1)









    



---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)
<ipython-input-18-315cedc8d7b6> in <module>()
      1 import sys
----> 2 result2 = pascals_triangle_2(sys.maxint - 1)

<ipython-input-16-57c82f468b3a> in pascals_triangle_2(k)
      8     # symmetric
      9     for n in xrange(k / 2):
---> 10         row.append(row[n] * (k - n) / (n + 1))
     11 
     12     # middle element is repeated only for odd values of k

MemoryError: